<!DOCTYPE html>
<html>
<!-- Created by GNU Texinfo 7.1, https://www.gnu.org/software/texinfo/ -->
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<!-- Copyright © 1988-2023 Free Software Foundation, Inc.

Permission is granted to copy, distribute and/or modify this document
under the terms of the GNU Free Documentation License, Version 1.3 or
any later version published by the Free Software Foundation; with the
Invariant Sections being "Funding Free Software", the Front-Cover
Texts being (a) (see below), and with the Back-Cover Texts being (b)
(see below).  A copy of the license is included in the section entitled
"GNU Free Documentation License".

(a) The FSF's Front-Cover Text is:

A GNU Manual

(b) The FSF's Back-Cover Text is:

You have freedom to copy and modify this GNU Manual, like GNU
     software.  Copies published by the Free Software Foundation raise
     funds for GNU development. -->
<title>Maintaining the CFG (GNU Compiler Collection (GCC) Internals)</title>

<meta name="description" content="Maintaining the CFG (GNU Compiler Collection (GCC) Internals)">
<meta name="keywords" content="Maintaining the CFG (GNU Compiler Collection (GCC) Internals)">
<meta name="resource-type" content="document">
<meta name="distribution" content="global">
<meta name="Generator" content="makeinfo">
<meta name="viewport" content="width=device-width,initial-scale=1">

<link href="index.html" rel="start" title="Top">
<link href="Option-Index.html" rel="index" title="Option Index">
<link href="index.html#SEC_Contents" rel="contents" title="Table of Contents">
<link href="Control-Flow.html" rel="up" title="Control Flow">
<link href="Liveness-information.html" rel="next" title="Liveness information">
<link href="Profile-information.html" rel="prev" title="Profile information">
<style type="text/css">
<!--
a.copiable-link {visibility: hidden; text-decoration: none; line-height: 0em}
span:hover a.copiable-link {visibility: visible}
-->
</style>


</head>

<body lang="en">
<div class="section-level-extent" id="Maintaining-the-CFG">
<div class="nav-panel">
<p>
Next: <a href="Liveness-information.html" accesskey="n" rel="next">Liveness information</a>, Previous: <a href="Profile-information.html" accesskey="p" rel="prev">Profile information</a>, Up: <a href="Control-Flow.html" accesskey="u" rel="up">Control Flow Graph</a> &nbsp; [<a href="index.html#SEC_Contents" title="Table of contents" rel="contents">Contents</a>][<a href="Option-Index.html" title="Index" rel="index">Index</a>]</p>
</div>
<hr>
<h3 class="section" id="Maintaining-the-CFG-1"><span>15.4 Maintaining the CFG<a class="copiable-link" href="#Maintaining-the-CFG-1"> &para;</a></span></h3>
<a class="index-entry-id" id="index-cfghooks_002eh"></a>

<p>An important task of each compiler pass is to keep both the control
flow graph and all profile information up-to-date.  Reconstruction of
the control flow graph after each pass is not an option, since it may be
very expensive and lost profile information cannot be reconstructed at
all.
</p>
<p>GCC has two major intermediate representations, and both use the
<code class="code">basic_block</code> and <code class="code">edge</code> data types to represent control
flow.  Both representations share as much of the CFG maintenance code
as possible.  For each representation, a set of <em class="dfn">hooks</em> is defined
so that each representation can provide its own implementation of CFG
manipulation routines when necessary.  These hooks are defined in
<samp class="file">cfghooks.h</samp>.  There are hooks for almost all common CFG
manipulations, including block splitting and merging, edge redirection
and creating and deleting basic blocks.  These hooks should provide
everything you need to maintain and manipulate the CFG in both the RTL
and <code class="code">GIMPLE</code> representation.
</p>
<p>At the moment, the basic block boundaries are maintained transparently
when modifying instructions, so there rarely is a need to move them
manually (such as in case someone wants to output instruction outside
basic block explicitly).
</p>
<a class="index-entry-id" id="index-BLOCK_005fFOR_005fINSN_002c-gimple_005fbb"></a>
<p>In the RTL representation, each instruction has a
<code class="code">BLOCK_FOR_INSN</code> value that represents pointer to the basic block
that contains the instruction.  In the <code class="code">GIMPLE</code> representation, the
function <code class="code">gimple_bb</code> returns a pointer to the basic block
containing the queried statement.
</p>
<a class="index-entry-id" id="index-GIMPLE-statement-iterators-1"></a>
<p>When changes need to be applied to a function in its <code class="code">GIMPLE</code>
representation, <em class="dfn">GIMPLE statement iterators</em> should be used.  These
iterators provide an integrated abstraction of the flow graph and the
instruction stream.  Block statement iterators are constructed using
the <code class="code">gimple_stmt_iterator</code> data structure and several modifiers are
available, including the following:
</p>
<dl class="ftable">
<dt><a id="index-gsi_005fstart-1"></a><span><code class="code">gsi_start</code><a class="copiable-link" href="#index-gsi_005fstart-1"> &para;</a></span></dt>
<dd><p>This function initializes a <code class="code">gimple_stmt_iterator</code> that points to
the first non-empty statement in a basic block.
</p>
</dd>
<dt><a id="index-gsi_005flast-1"></a><span><code class="code">gsi_last</code><a class="copiable-link" href="#index-gsi_005flast-1"> &para;</a></span></dt>
<dd><p>This function initializes a <code class="code">gimple_stmt_iterator</code> that points to
the last statement in a basic block.
</p>
</dd>
<dt><a id="index-gsi_005fend_005fp-1"></a><span><code class="code">gsi_end_p</code><a class="copiable-link" href="#index-gsi_005fend_005fp-1"> &para;</a></span></dt>
<dd><p>This predicate is <code class="code">true</code> if a <code class="code">gimple_stmt_iterator</code>
represents the end of a basic block.
</p>
</dd>
<dt><a id="index-gsi_005fnext-1"></a><span><code class="code">gsi_next</code><a class="copiable-link" href="#index-gsi_005fnext-1"> &para;</a></span></dt>
<dd><p>This function takes a <code class="code">gimple_stmt_iterator</code> and makes it point to
its successor.
</p>
</dd>
<dt><a id="index-gsi_005fprev-1"></a><span><code class="code">gsi_prev</code><a class="copiable-link" href="#index-gsi_005fprev-1"> &para;</a></span></dt>
<dd><p>This function takes a <code class="code">gimple_stmt_iterator</code> and makes it point to
its predecessor.
</p>
</dd>
<dt><a id="index-gsi_005finsert_005fafter-1"></a><span><code class="code">gsi_insert_after</code><a class="copiable-link" href="#index-gsi_005finsert_005fafter-1"> &para;</a></span></dt>
<dd><p>This function inserts a statement after the <code class="code">gimple_stmt_iterator</code>
passed in.  The final parameter determines whether the statement
iterator is updated to point to the newly inserted statement, or left
pointing to the original statement.
</p>
</dd>
<dt><a id="index-gsi_005finsert_005fbefore-1"></a><span><code class="code">gsi_insert_before</code><a class="copiable-link" href="#index-gsi_005finsert_005fbefore-1"> &para;</a></span></dt>
<dd><p>This function inserts a statement before the <code class="code">gimple_stmt_iterator</code>
passed in.  The final parameter determines whether the statement
iterator is updated to point to the newly inserted statement, or left
pointing to the original  statement.
</p>
</dd>
<dt><a id="index-gsi_005fremove-1"></a><span><code class="code">gsi_remove</code><a class="copiable-link" href="#index-gsi_005fremove-1"> &para;</a></span></dt>
<dd><p>This function removes the <code class="code">gimple_stmt_iterator</code> passed in and
rechains the remaining statements in a basic block, if any.
</p></dd>
</dl>

<a class="index-entry-id" id="index-BB_005fHEAD_002c-BB_005fEND"></a>
<p>In the RTL representation, the macros <code class="code">BB_HEAD</code> and <code class="code">BB_END</code>
may be used to get the head and end <code class="code">rtx</code> of a basic block.  No
abstract iterators are defined for traversing the insn chain, but you
can just use <code class="code">NEXT_INSN</code> and <code class="code">PREV_INSN</code> instead.  See <a class="xref" href="Insns.html">Insns</a>.
</p>
<a class="index-entry-id" id="index-purge_005fdead_005fedges-1"></a>
<p>Usually a code manipulating pass simplifies the instruction stream and
the flow of control, possibly eliminating some edges.  This may for
example happen when a conditional jump is replaced with an
unconditional jump.  Updating of edges
is not transparent and each optimization pass is required to do so
manually.  However only few cases occur in practice.  The pass may
call <code class="code">purge_dead_edges</code> on a given basic block to remove
superfluous edges, if any.
</p>
<a class="index-entry-id" id="index-redirect_005fedge_005fand_005fbranch_002c-redirect_005fjump"></a>
<p>Another common scenario is redirection of branch instructions, but
this is best modeled as redirection of edges in the control flow graph
and thus use of <code class="code">redirect_edge_and_branch</code> is preferred over more
low level functions, such as <code class="code">redirect_jump</code> that operate on RTL
chain only.  The CFG hooks defined in <samp class="file">cfghooks.h</samp> should provide
the complete API required for manipulating and maintaining the CFG.
</p>
<a class="index-entry-id" id="index-split_005fblock"></a>
<p>It is also possible that a pass has to insert control flow instruction
into the middle of a basic block, thus creating an entry point in the
middle of the basic block, which is impossible by definition: The
block must be split to make sure it only has one entry point, i.e. the
head of the basic block.  The CFG hook <code class="code">split_block</code> may be used
when an instruction in the middle of a basic block has to become the
target of a jump or branch instruction.
</p>
<a class="index-entry-id" id="index-insert_005finsn_005fon_005fedge"></a>
<a class="index-entry-id" id="index-commit_005fedge_005finsertions"></a>
<a class="index-entry-id" id="index-gsi_005finsert_005fon_005fedge-1"></a>
<a class="index-entry-id" id="index-gsi_005fcommit_005fedge_005finserts-1"></a>
<a class="index-entry-id" id="index-edge-splitting"></a>
<p>For a global optimizer, a common operation is to split edges in the
flow graph and insert instructions on them.  In the RTL
representation, this can be easily done using the
<code class="code">insert_insn_on_edge</code> function that emits an instruction
&ldquo;on the edge&rdquo;, caching it for a later <code class="code">commit_edge_insertions</code>
call that will take care of moving the inserted instructions off the
edge into the instruction stream contained in a basic block.  This
includes the creation of new basic blocks where needed.  In the
<code class="code">GIMPLE</code> representation, the equivalent functions are
<code class="code">gsi_insert_on_edge</code> which inserts a block statement
iterator on an edge, and <code class="code">gsi_commit_edge_inserts</code> which flushes
the instruction to actual instruction stream.
</p>
<a class="index-entry-id" id="index-verify_005fflow_005finfo"></a>
<a class="index-entry-id" id="index-CFG-verification"></a>
<p>While debugging the optimization pass, the <code class="code">verify_flow_info</code>
function may be useful to find bugs in the control flow graph updating
code.
</p>

</div>
<hr>
<div class="nav-panel">
<p>
Next: <a href="Liveness-information.html">Liveness information</a>, Previous: <a href="Profile-information.html">Profile information</a>, Up: <a href="Control-Flow.html">Control Flow Graph</a> &nbsp; [<a href="index.html#SEC_Contents" title="Table of contents" rel="contents">Contents</a>][<a href="Option-Index.html" title="Index" rel="index">Index</a>]</p>
</div>



</body>
</html>
